package org.langqiao.algorithm;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.List;
import java.util.Collections;
import java.util.Arrays;

/*整数的划分问题
 * 如，对于正整数n=6，可以分划为： 
6 
5+1 
4+2, 4+1+1 
3+3, 3+2+1, 3+1+1+1 
2+2+2, 2+2+1+1,2+1+1+1+1 
1+1+1+1+1+1+1 
现在的问题是给定任意的整数n，打印出所有的划分，试编写算法，用户从键盘输入n，输出整数的所有划分。
 */
public class IntDivision {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		List[] expressions = new List[x]; 
		for(int i=1;i<x;i++) {
			if(i==1) {
				expressions[i-1] = new ArrayList();
				expressions[i-1].add("1");
			} else {
				expressions[i-1]=new ArrayList();
				expressions[i-1].add(String.valueOf(i));
				for(int j=i-1;j>=i/2;j--)
				{
					for(int k=0;k<expressions[j-1].size();k++)
					{
						String str1=(String)expressions[j-1].get(k);//原来的表达式
						String str2=process(str1+"+"+(i-j));//排序后的表达式
						boolean b=false;//查找是否已经存在
						for(int kk=0;kk<expressions[i-1].size();kk++)
						{
							if(expressions[i-1].get(kk).toString().equals(str2))
							{
								b=true;
								break;
							}
						}
						if(!b)
						{
							expressions[i-1].add(str2);
						}
					}
				}
			}
				
		}
		Collections.sort(expressions[x-1]);
		String temp=null;
		for(int i=expressions[x-1].size()-1;i>=0;i--)
		{
			String value=expressions[x-1].get(i).toString();
			if(temp==null)
			{
				System.out.print(value);
				temp=value.substring(0,1);
			}
			else
			{
				if(value.startsWith(temp))
				{
					System.out.print(",");
				}
				else
				{
					System.out.println();
					temp=value.substring(0,1);
				}
				System.out.print(value);
			}
		}
	}
	
	/*主方法结束
	 * 自定义一个方法process来实现自动排序功能，比如3+1+2+1，调整为3+2+1+1
	 */
	static String process(String exp) {
		exp=exp.replace("+"," ");
		String str[]=exp.split(" ");
		Arrays.sort(str);
		StringBuffer sb=new StringBuffer();
		for(int i=0;i<str.length-1;i++)
		{
			sb.append(str[i]+"+");
		}
		sb.deleteCharAt(sb.length()-1);
		return sb.toString();
	}
}
